package review.linkedList;

public class DoubleLinkedListSentinel<E> {
    class Node {
        Node prev;
        E val;
        Node next;

        public Node(Node prev, E val, Node next) {
            this.prev = prev;
            this.val = val;
            this.next = next;
        }
    }

    Node head = new Node(null, null, null);
    Node tail = new Node(null, null, null);

    public DoubleLinkedListSentinel() {
        head.next = tail;
        tail.prev = head;
    }


    public boolean addFirst(E val) {
        int i = -1;
        head.next = new Node(head, val, head.next);
        return true;
    }


    public boolean addLast(E val) {
        Node prev = tail.prev;
        Node inserted = new Node(prev, val, tail);
        prev.next = tail;
        tail.prev = prev;
        return true;
    }

    public boolean insert(int index, E val) {
        if (index < 0) {
            throw new IndexOutOfBoundsException("index must be non-negative");
        }
        Node prev = head;
        int i = -1;
        while (prev != tail && i != index - 1) {
            prev = prev.next;
            i++;
        }
        if (prev == tail) {
            throw new IndexOutOfBoundsException("index[" + index + "] out of bounds");
        }
        Node next = prev.next;
        Node inserted = new Node(prev, val, next);
        prev.next = inserted;
        next.prev = inserted;
        return true;
    }


    public E get(int index) {
        if (head == null) {
            throw new IndexOutOfBoundsException("list is empty");
        }
        int i = 0;
        Node p = head.next;
        while (p != tail && i != index) {
            i++;
            p = p.next;
        }
        if(p==null){
            throw new IndexOutOfBoundsException("index[" + index + "] out of bounds");
        }
        return p.val;
    }


    public E removeFirst() {
        Node next = head.next;
        if(next == tail){
            throw new IndexOutOfBoundsException("list is empty");
        }
        E val = head.next.val;
        head.next = next.next;
        next.next.prev = head;
        return val;
    }


    public E remove(int index) {
        Node prev = head;
        int i = -1;
        while(prev!=tail && i!=index-1){
            i++;
            prev =prev.next;
        }
        if(prev == null){
            throw new IndexOutOfBoundsException("index[" + index + "] out of bounds");
        }
        Node removed = prev.next;
        if(removed == null){
            throw new IndexOutOfBoundsException("index[" + index + "] out of bounds");
        }
        prev.next = removed.next;
        removed.next.prev = prev;
        return removed.val;
    }


}
